A tremendous need exists for systems and methods which can lossless compress sampled digital data. An application to which the present invention pertains involves the lossless compression of grey scale or color data of video images, such as exists in medical imaging applications.
High definition digital video images with multiple bits per sampled pixel require the lossless compression of data representing millions of pixels at data rates in the range of tens of megabytes per second for compression and decompression. Though lossless sliding window Lempel-Ziv algorithms have been implemented in hardware with sufficient throughput rates, the compression ratios of multiple bit per sampled pixel position data has been relatively poor. In part, this is attributable to the fact that as the quantization precision (in bits per sample) increases, so too does the likelihood that successively adjacent pixels will differ in the least significant bit positions of the digital data. Though preprocessing techniques have been developed, such as that described in the aforementioned co-pending U.S. patent application Ser. No. 08/409,766, the techniques presume a relatively low precision in the data samples and therefore a corresponding consistency of the sampled data in adjacent regions along a scan line. As the bit count per sampled pixel position increases, as with high definition grey scale or RGB format color images, the consistency of the data from pixel-to-pixel decreases dramatically.
Though sampled image data contains a great deal of information redundancy it does not compress well with a direct application of the Lempel-Ziv algorithm. Lempel-Ziv sliding window data compression achieves compression by finding identical matching strings of bytes in an input data stream. In sampled image data, a pixel is represented by an intensity value, or a RGB color content value, captured by digital to analog conversion. A typical high definition video image will have 16 bits per grey scale pixel or 24 bits per color pixel. Although large sections of the image may appear of the same intensity in casual observation, noise variations alone will cause changes in the lower order bits for adjacent pixels. For example for a 16 bit per pixel sample representing a grey scale pixel, noise variation of one part in approximately 65,000 will be sufficient to distinguish successive pixel data.
Grouping pixel data to improve compression is described in U.S. Pat. No. 5,416,857. However, the technique described in the patent does not employ the highly desirable Lempel-Ziv algorithm as first described in the article entitled "A Universal Algorithm for Sequential Data Compression" by authors Lempel and Ziv, in IEEE Transactions on Information Theory, Vol. IT-23, No. 3, pp. 337-343 in 1977. Furthermore, the technique disclosed in the patent involves the processing of the data through a unique circuit in contrast to a preprocessing implementation employing a conventional video graphics system frame buffer.
Therefore, there remains a need for systems and methods which process sampled data into a format particularly amenable lossless sliding window Lempel-Ziv data compression.